package leetcode;


public class UniquePath {

	public static void main(String[] args) {
		int[][] obstacleGrid = {{0, 0}, {0, 0}};
		UniquePath object = new UniquePath();
		object.uniquePaths2(4, 6);
		System.out.println("-----");
		object.uniquePaths3(4, 6);
		System.out.println("----------");
		object.uniquePathsWithObstacles(obstacleGrid);
	}
	
	
	// 一共要走m + n - 2步，选择任意的n - 1步走
	// C(m + n - 2, n - 1)
	public long uniquePaths(int m, int n) {
		if (m == 1 || n == 1){
			return 1;
		}
		//将m和n变成向右或向下走的步数
		m--;
		n--;
		if (m < n) { // Swap, so that m is the bigger number
			m = m + n;
			n = m - n;
			m = m - n;
		}
		long res = 1;
		int j = 1;
		//C(m + n - 2, n - 1) = P(n + m) / (P(n) * P(m))
		//我们已经将m变为大值了，所以等于(m + 1) *...*(m + n)  / P(n)
		
		// Instead of taking factorial, keep on multiply & divide
		for (int i = m + 1; i <= m + n; i++, j++) { 
			res *= i;
			res /= j;
		}
		return res;
	}
	
	//使用动态规划来做
	public int uniquePaths2(int m, int n) {
		if (m == 1 || n == 1) {
			return 0;
		}
		int[][] dp = new int[m][n];
		for (int i = 0; i < m; i++) {
			dp[i][0] = 1;
		}
		for (int j = 0; j < n; j++) {
			dp[0][j] = 1;
		}
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				System.out.print(dp[i][j] + "  ");
			}
			System.out.println();
		}
		return dp[m - 1][n - 1];
	}
	
	// 使用动态规划来做, 降低空间复杂度
	public int uniquePaths3(int m, int n) {
		if (m == 1 || n == 1) {
			return 0;
		}
		if(m < n){
			int temp = m;
			m = n;
			n = temp;
		}
		int[] dp = new int[m];
		for (int i = 0; i < m; i++) {
			dp[i] = 1;
		}
//		int last = 0;
//		for (int i = 1; i < n; i++) {
//			last = 0;
//			for (int j = 0; j < m; j++) {
//				dp[j] = dp[j] + last;
//				last = dp[j];
//			}
//		}
		
		//上面的代码可以进一步更新成这样
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < m; j++) {
				dp[j] = dp[j] + dp[j - 1];
			}
		}
		for (int i = 0; i < m; i++) {
			System.out.print(dp[i] + "  ");
		}
		System.out.println();
		return dp[m - 1];
	}
		
	//当有障碍的时候，就只能使用动态规划来做了
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		if(obstacleGrid == null || obstacleGrid[0] == null ){
			return 0;
		}
		int rows = obstacleGrid.length;
		int cols = obstacleGrid[0].length;
		if(rows <= 0 || cols <= 0){
			return 0;
		}
		int[][] dp = new int[rows][cols];
		if(obstacleGrid[0][0] != 0 || obstacleGrid[rows - 1][cols - 1] != 0){
			return 0;
		}
		for (int i = 0; i < rows; i++) {
			if(obstacleGrid[i][0] != 0){
				break;
			}else{
				dp[i][0] = 1;
			}
		}
		for (int j = 0; j < cols; j++) {
			if(obstacleGrid[0][j] != 0){
				break;
			}else{
				dp[0][j] = 1;
			}
		}
		for (int i = 1; i < rows; i++) {
			for (int j = 1; j < cols; j++) {
				if(obstacleGrid[i][j] == 0){
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				}
			}
		}
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				System.out.print(dp[i][j] + "  ");
			}
			System.out.println();
		}
		return dp[rows - 1][cols - 1];
	}
}
